package 前缀和;

import java.util.HashMap;
import java.util.Map;
//同余定理  （a-b）/p = k无余数 -》 a%p = b%p
// 修正 负数%正数 = 负数   ------(a%p+p）% p 结果为正数

public class 和可被K整除的子数组 {
    public int subarraysDivByK(int [] nums,int k){
        Map<Integer,Integer> hash = new HashMap<Integer, Integer>();
        hash.put(0,1);
        int sum = 0,ret = 0;
        for(int x : nums){
            sum+=x;// 计算当前位置的前缀和
            int mod = (sum%k+k)%k;
            ret+=hash.getOrDefault(mod,0);//统计结果
            hash.put(mod,hash.getOrDefault(mod,0)+1);

        }
        return ret;
    }
}
